Skip to main content

Concatenated Words

Question​

Given a list of words (without duplicates), please write an algorithm to find all concatenated words in the given list.

Example 1
None

Solution​

all//Concatenated Words.py


"""
"""
def findConcatenatedWords(words):

    # Create an empty set to store all
    # the concatenated words
    resultSet = set()

    # Loop through all the words given in the
    # input list
    for word in words:

        # If the current word is empty
        # then continue
        if len(word) == 0:
            continue

        # If the current word is already present
        # in the result set then continue
        if word in resultSet:
            continue

        # Flag variable to tell if the current
        # word can be formed using words already
        # present in the result set
        flag = 0

        # Create a temporary set which will store
        # all the concatenated words which will be
        # formed by the current word
        tmp = set()

        # Loop through all the characters of the
        # current word
        for i in range(len(word)):

            # Slice the word from 0 to i + 1
            # to check if it is present in the
            # result set
            if word[:i + 1] in resultSet:
                flag = 1

                # If the word is present in the result
                # set then add the sliced word to the
                # temporary set
                tmp.add(word[:i + 1])

        # If flag is 1 then it means that the
        # current word can be formed using the
        # words present in the result set
        # Hence add the word to the result set
        if flag == 1:
            resultSet.add(word)

        # Union the temporary set with the result set
        resultSet = resultSet | tmp

    # Return the result set
    return resultSet

# Driver Code
words = ["cat", "cats", "catsdogcats",
         "dog", "dogcatsdog", "hippopotamuses",
         "rat", "ratcatdogcat"]

print(findConcatenatedWords(words))